ABSTRACT DATA TYPES

Tags: #◇Computer Science #◇CSADPRG #◇Conceptual #◇Abstract Data Types

◇Overview

Abstraction is a fundamental concept in programming that reduces complexity by removing irrelevant information and highlighting important attributes, allowing entities to be grouped based on common characteristics. Data abstraction involves the use of abstract data types (ADTs), enclosures that bundle data representations with subprograms to manipulate them. This module covers the theoretical principles of ADTs, their language design issues, and implementations in object-oriented languages like C++ and Java.

◇Key Definitions

• Abstraction: A view or representation of an entity that includes only the most significant attributes, hiding irrelevant details.
• Process Abstraction: Using subprograms to encapsulate logic, one of the oldest concepts in programming language design.
• Abstract Data Type (ADT): An enclosure that includes both the data representation of a specific type and the operations (subprograms) allowed on that type.
• Object: An instance of an abstract data type.
• Information Hiding: A principle where the actual data representation is hidden from the user, preventing direct manipulation and enforcing access via specified operations.
• Encapsulation: A grouping of logically related subprograms into a unit that can be separately compiled, addressing the needs for code organization and partial compilation.
• Constructors: Functions used to initialize the data members of an instance and sometimes allocate storage (e.g., heap-dynamic).
• Destructors: Functions meant for cleanup after an instance's lifetime ends, often used to reclaim heap storage.

◇Theoretical Framework / Concepts

Built-in vs User-Defined ADTs

All built-in data types (like floating-point types) are inherently abstract data types because their actual implementation is hidden from the user, and they can only be manipulated via predefined operations.
For user-defined abstract data types to have the same characteristics, they must satisfy two conditions:

1. Hidden Representation: The type definition must allow program units to declare variables, but the representation itself must be hidden. The only direct operations possible are those explicitly provided.
2. Single Syntactic Unit: The declarations of the type and the protocols of its operations (which provide the interface) must be contained in a single syntactic unit. The interface remains independent of the underlying representation.

Benefits of Abstraction

• Reliability: Restricting user manipulation of internal object representation increases code reliability.
• Simplicity: Reduces the number of variables and the range of code a developer needs to track.
• Flexibility: Developers can change internal structures and operations without directly affecting the users/programmers relying on the interface.

Access Controls

Language designers provide mechanisms to control visibility:

• Accessor Methods: Getters and setters that offer restricted direct access to data.
• Access Modifiers: Keywords (e.g., public, private, protected) that specify levels of visibility. Some languages (like Ruby) restrict public access more strictly.

Language Design Issues for ADTs

When designing languages that support ADTs, creators must decide:

1. Can abstract types be parameterized?
2. What specific access controls should be provided?
3. Should the specification of the type be physically separated from its implementation?

◇Examples

C++ Implementations

C++ supports ADTs via the class construct, derived from C structs and Simula 67 classes.

• Data Members & Member Functions: Instances have their own copies of data members, but share a single copy of member functions.
• Information Hiding: Enforced via clauses like private (hidden), public (visible), and protected (visible to subclasses).
• Friend Functions: C++ uses "friend" functions/classes to grant private member access to specific, unrelated units.

Example: A basic C++ class with access modifiers:

class Base {
public: 
    int publicMember;
protected: 
    int protectedMember;
private: 
    int privateMember; 
};

Example: C++ Stack Implementation (Constructors & Destructors):

class Stack {
private: 
    int *stackPtr;
    int maxLen;
    int topSub; 
public:
    Stack() { // Constructor
        stackPtr = new int [100];
        maxLen = 99;
        topSub = -1;
    }
    ~Stack() { // Destructor
        delete [] stackPtr;
    }
    void push(int number) { /*...*/ }
    void pop() { /*...*/ }
    int top() { /*...*/ }
    int empty() { /*...*/ }
};

Java Implementations

Java is similar to C++ but has notable differences:

• All user-defined types are classes.
• All objects are heap-allocated and accessed exclusively through reference variables.
• Access control modifiers are applied per individual entity rather than using C++-style grouped clauses.
• Package Scope: Instead of C++ "friends", Java uses package scoping where entities in the same package lacking explicit access modifiers are mutually visible.

Encapsulation Examples Across Languages

• C: Header files
• C++: Header and implementation files, classes, namespaces
• C#: Assembly files, namespaces
• Java: JAR files, packages
• Ada: Packages
• Ruby: Modules

◇References & Navigation

• Previous Topic: ◇Subprograms
• Related Notes: ◇Classes and Objects, ◇Data Structures